function quickSort(arr,left,right){
    if (left>=right){
        return;
    }
    const index = partition(arr, left, right);
    quickSort(arr, left,index-1);
    quickSort(arr,index+1, right);
}
function partition(arr, left, right){
    // 1.选择基准元素, 初始化i,j指针
    const base = arr[left];
    let i = left;
    let j = right;
    while(i < j){
        // 从右往左扫
        while(i < j && arr[j] >= base){
            j--;
        }
        // 从左往右扫
        while(i < j && arr[i] <= base){
            i++;
        }
        if (i<j){
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    // 交换基准元素的值
    [arr[left], arr[i]] = [arr[i], arr[left]];
    // 返回基准元素的索引
    return i;
}
// 测试代码
let arr = [10, 7, 8, 9, 1, 5];
console.log("排序前:", arr);
quickSort(arr, 0, arr.length - 1);
console.log("排序后:", arr);